package com.leecode;

import com.test.TreeNode;

/**
 * 543. 二叉树的直径
 * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度
 * 中的最大值。这条路径可能穿过也可能不穿过根结点。
 *
 * 示例 :
 * 给定二叉树
 *
 *           1
 *          / \
 *         2   3
 *        / \
 *       4   5
 *
 * 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
 */
public class Leet543 {
	public static void main(String[] args) {

	}
	/**
	 * 考点:
	 * 思路:要么过root(res=左子树层数+右子树层数),要么不过(max(diamater(root.left),diamater(root.right))),第二次做的时候
	 * 把思路给忘了,但是大部分是0ms,我是23ms?!!
	 * 思路2:先做另一题:输出每个节点树的层数,再转换思维到"遍历每个节点的左deep+右deep,取节点返回结果的max"
	 * 100%,87%,
	 */
	int res=-1;
	public int diameterOfBinaryTree(TreeNode root) {
		if(root==null)return 0;

		deep(root);
		return res;
	}

	public int deep(TreeNode root){
		if(root==null)return 0;

		int left = deep(root.left);
		int righ = deep(root.right);
		if(left+righ>res)res=left+righ;
		return Math.max(left,righ)+1;
	}
}
